package com.example.yin.sorting;

/**
 * @Author huaiyu yin
 * @Date 2021/7/6 10:09 上午
 * @Version 1.0
 */
public class QuickSort {
    /**
     * 快速排序是对冒泡排序的一种改进。
     * 它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，
     * 其中一部分的所有数据都比另外一部分的所有数据都要小，
     * 然后再按次方法对这两部分数据分别进行快速排序，
     * 整个排序过程可以递归进行，
     * 以此达到整个数据变成有序序列。
     * 最坏情况的时间复杂度为O(n2)，最好情况时间复杂度为O(nlog2n)。
     * 快速排序由冒泡排序演变而来，冒泡排序原理：
     *
     * 1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
     *
     * 2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
     *
     * 3、针对所有的元素重复以上的步骤，除了最后一个。
     *
     * 4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
     *
     * 示例如下：
     * arr = [2,4,6,8,65,4,45,55,34]
     * 第一次比较，取第一个数值和最后一个数值作为初始arr[0],arr[8]
     * 设定一个比较值一般是第一个元素arr[0],
     * 分别从0向前和从8向后取数值比较
     * 2和34比较34比较，34比2大不交换放到2的右边
     * 第二轮55同2比较，55比2大不需要转移
     * 第三轮4同55比较，55比四大不需要转移
     * 第四轮45同4比较，45比4大不需要用转移
     * 第五轮6同45比较，6比45小不需要转移
     * 第六轮4和6比较，4比6小交换位置，为[2，4，4，8，65，6，45，55，34]
     * 第七轮8和6比较，8比6大交换位置，为[2，4，4，6，65，8，45，55，34]
     * 第八轮8和65比较，8比65小交换位置，为[2，4，4，6，8，65，45，55，34]
     * 第一轮结束此时8为中间值，区分为两个数组，左边所有数值都比中间值（8）小[2，4，4，6]，右边都比中间值大[65，45，55，34]
     * 至此根据下标区分当作两个数组分别作相同的操作，直至数组无法再进行排序为止。结束排序
     */
    public static void main(String[] args) {
        //初始化一个数组
        int[] arr = {2,4,6,8,65,4,45,1,55,34};
        toSort(arr,0,arr.length-1);
        System.out.println(arr.toString());

    }


    static void toSort(int[] li, int i, int j){
        if(i<j){
            int temp = li[i];
            while (i<j) {
                while ((i < j) && (li[i] <= li[j])) {
                    j--;
                }
                li[i] = li[j];
                while ((i < j) && (li[j] >= li[i])) {
                    i++;
                }
                li[j] = li[i];


            }
            li[i] = temp;
            toSort(li,0,i-1);
            toSort(li,i+1,li.length-1);
        }

    }
    //交换操作
    static void  change(int[] li, int i, int j){
        li[i] = li[i]^li[j];
        li[j] = li[i]^li[j];
        li[i] = li[i]^li[j];
    }


}
